package woa.recursion;

/**
 * 第K个语法符号
 * 在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
 * 给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
 *
 * @author wangpeng
 * @date 2021/12/15
 */
public class KthGrammar {

    public static int kthGrammar(int n, int k) {
        if (n == 1) {
            return 0;
        }

        int length = (int) Math.pow(2, n - 1);
        if (k > length / 2) {
            int i = kthGrammar(n - 1, k - length / 2);
            return i == 0 ? 1 : 0;
        }

        return kthGrammar(n - 1, k);
    }

    public static void main(String[] args) {
        System.out.println(kthGrammar(4, 5));
    }

}
